package main.java.com.gxc.string;

import java.util.Arrays;

/**
 * 最长特殊序列
 *
 * 给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
 *
 * 特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
 *
 *  s 的 子序列可以通过删去字符串 s 中的某些字符实现。
 *
 * 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
 *
 *
 * 示例 1：
 *
 * 输入: strs = ["aba","cdc","eae"]
 * 输出: 3
 * 示例 2:
 *
 * 输入: strs = ["aaa","aaa","aa"]
 * 输出: -1
 *
 *
 * 逻辑：
 * 1、遍历字符串数组，倒序
 * 2、遍历字符串，判断是否存在相等的字符串，如果不存在，则返回最大长度，如果存在则继续遍历
 * 3、在剩余长度判断是否存在相等的字符串，如果不存在，则判断是否是长字符串的子序列，如果不是，则返回最大长度，如果存在则继续遍历
 */
public class FindLUSlength {

    public static void main(String[] args) {
        //String[] strs = {"aba", "cdc", "eae"};
        String[] strs = {"aaa","aaa","aa"};
        //String[] strs = {"a","b","c","d","e","f","a","b","c","d","e","f"};
        //String[] strs = {"aabbcc", "aabbcc","cb"};
        //System.out.println(process(strs));

        System.out.println(guanfang(strs));
    }

    public static int process(String[] strs) {
        //字符串按长度倒序  时间复杂度 n的平方
        for (int i = 0; i < strs.length; i++) {
            for (int j = i+1; j < strs.length; j++) {
                if (strs[i].length()<strs[j].length()) {
                    String str = strs[i];
                    strs[i] = strs[j];
                    strs[j] = str;
                }
            }
        }

        for (int i = 0; i < strs.length; i++) {
            boolean isSame = false;
            for (int j = 0; j < strs.length; j++) {
                if (strs[i].length() == strs[j].length()) {
                    if (strs[i].equals(strs[j])) {
                        isSame = true;
                        break;
                    }
                } else {
                    for (int q = 0; q < j; q++) {
                        boolean subseq = is_subseq(strs[q], strs[j]);
                        if (!subseq) return strs[j].length();
                    }
                }
            }
            if (!isSame) return strs[i].length();
        }

        return -1;
    }



    /**
     * 判断str1 是否是str2 的子序列。 str1.length()  < str2.length()
     *  双指针判断
     * @param s1
     * @param s2
     * @return
     */
    public static boolean is_subseq(String s1, String s2) {
        String str1 = s1;
        String str2 = s2;
        if (str1.length()>str2.length()) {
            str1 = s2;
            str2 = s1;
        }
        int index1 = 0;
        int index2 = 0;
        while (index1<str1.length() && index2<str2.length()) {
            if (str1.charAt(index1) == str2.charAt(index2)) {
                index1++;
            }
            index2++;
        }
        //如果短字符串的指针走到最后，说明str2 是 str1 的子序列
        return index1 == str1.length();
    }

    //官方解
    public static int guanfang(String[] strs) {
        int n = strs.length;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            boolean check = true;
            for (int j = 0; j < n; ++j) {
                if (i != j && is_subseq(strs[i], strs[j])) {
                    check = false;
                    break;
                }
            }
            if (check) {
                ans = Math.max(ans, strs[i].length());
            }
        }
        return ans;
    }

}
